package recursionToDP;
import java.util.Stack;
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Arrays;
/*
 * 动态规划 : 关注的 是解 的个数
 * 回溯:   解 的个数 和解 的 集合 都可以做到
 * 去重 和 剪枝的  操作 要有
 * 给定一个 数组 用数组的 数据 组成 sum 为 target 的 方案 组合  或者 方法数     (数组中的数据 可以重复选取)
 * 如果数组 中元素   无 重复值的 话  那就不用 去重了
 */
public class backTracingAndDP {
	public static void main(String []args) {
		//System.out.println("hhhh");
		int arr[]= {6,5,4,3};
		func(arr,10);
		System.out.println(backTrace(arr,10,0));
		System.out.println(func1(arr,10));
		System.out.println(DP(arr,10));
		System.out.println(dp(arr,10));
	}
	
	public static int dp(int arr[] ,int aim) {
		int N=arr.length;
		int dp [][] =new int [N+1][aim+1];
		dp[N][0]=1;
		for(int index = N-1; index>=0 ;index--) {
			for(int rest = 0; rest <= aim; rest++) {
				int ways=0;
				for(int zhang = 0;zhang*arr[index] <= rest ;zhang++) {
					ways+=dp[index+1][rest-zhang*arr[index]];
				}
				dp[index][rest]=ways;
			}
		}
		for(int a[] : dp) {
			for(int value : a) {
				System.out.print(value+" ");
			}
			System.out.println();
		}
		return dp[0][aim];
	}
	//纯暴力 递归呢 ??
//	public static void backing(int arr[],int target,int) {
//		
//	}
	
	//  下面 是 递归 回溯 
	public static void func(int arr[],int target) {
		// 加一些过滤 条件  这里 就不写了
		Arrays.sort(arr);
		List<LinkedList<Integer>> ans=new ArrayList<>();
		LinkedList<Integer> path=new LinkedList<>();
		backTracing(arr,target,0,path,ans);
		for(LinkedList<Integer> path1 : ans) {
			System.out.println(path1);
		}
	}
	// 数组中   无重复值   下面 给出 DP
	public static int DP(int arr[] ,int aim) {
		// 过滤条件
		int N = arr.length;
		int dp [][] =new int [N][aim+1];
		// N  行 target +1 列   其中 第零列  的每一行都是 0 
		for(int i=0;i<N;i++) {
			dp[i][0]=1;
		}
		for(int target=1;target<=aim;target++) {
			for(int index=N-1 ;index >=0 ; index--) {
//			if(i>index && arr[i]==arr[i-1]) {
//				continue;
//			}
				int ans=0;
				for(int i=index;i<arr.length &&  target-arr[i]>=0;i++) {
					ans+=dp[i][target-arr[i]];
				}
				dp[index][target]=ans;
			}
			
		}
		for(int a[] : dp) {
			for(int value : a) {
				System.out.print(value+" ");
			}
			System.out.println();
		}
		return dp[0][aim];
	}
	//  纯暴  力 递归 
	public static int func1(int arr[], int target) {
		return recursion(arr,target,0);
		
	}
	public static int recursion(int arr[] ,int target ,int index) {
		if(target==0) {
			return 1;
		}
		int ans=0;
		for(int i=index ;i< arr.length  && target-arr[i]>=0;i++) {
			if(i>index && arr[i]==arr[i-1]) {
				continue;
			}
//			target-=arr[i];
			ans+=recursion(arr,target-arr[i],i);
//			target+=arr[i];	
		}
		return ans;
	}
	//  剪枝 之后的 带返回值的 回溯
	public static int backTrace(int arr[],int target,int index) {
		//  剪枝 操作 后 这行代码  就不会 执行了
//		if(curSum>target) {
//			return ;
//		}
		if(target==0) {
//			ans.add(new LinkedList<>(path));
			return 1;
		}
		int ans=0;
		for(int i=index; i<arr.length && target-arr[i]>=0 ;i++) {
			//  这里 为啥  这个 去重操作 对于 下一次 从i 开始 而不是从 i+1 开始的 也是 奏效的 ？？？？？
			//  那这样 还有 used 数组 什么事情  这里  绝对有些东西 在里面
			if(i>index && arr[i]==arr[i-1]) {
				continue;
			}
//			path.add(arr[i]);
			//target-=arr[i]; 牛逼 牛逼   牛逼 牛逼比u比  比u比牛逼  牛逼 牛逼牛逼 牛逼   牛逼 牛逼比u比  比u比牛逼  牛逼 牛逼
			ans+=backTrace(arr,target-arr[i],i);
//			path.removeLast();
			//target+=arr[i];
		}
		return ans;
	}
	//  减少参数的   函数 也完成 了
	public static void backTracing(int arr[],int target,int index,LinkedList<Integer> path,
			List<LinkedList<Integer>> ans) {
		//  剪枝 操作 后 这行代码  就不会 执行了
//		if(curSum>target) {
//			return ;
//		}
		if(target==0) {
			ans.add(new LinkedList<>(path));
			return ;
		}
		for(int i=index; i<arr.length && target-arr[i]>=0 ;i++) {
			//  这里 为啥  这个 去重操作 对于 下一次 从i 开始 而不是从 i+1 开始的 也是 奏效的 ？？？？？
			//  那这样 还有 used 数组 什么事情  这里  绝对有些东西 在里面
			if(i>index && arr[i]==arr[i-1]) {
				continue;
			}
			path.add(arr[i]);
			target-=arr[i];
			backTracing(arr,target,i,path,ans);
			path.removeLast();
			target+=arr[i];
		}
	}
/*
 * 
 * 	
	public static void backTracing(int arr[],int target,int index,LinkedList<Integer> path,
			List<LinkedList<Integer>> ans,int curSum) {
		//  剪枝 操作 后 这行代码  就不会 执行了
//		if(curSum>target) {
//			return ;
//		}
		if(curSum==target) {
			ans.add(new LinkedList<>(path));
			return ;
		}
		for(int i=index; i<arr.length &&curSum+arr[i]<=target ;i++) {
			//  这里 为啥  这个 去重操作 对于 下一次 从i 开始 而不是从 i+1 开始的 也是 奏效的 ？？？？？
			//  那这样 还有 used 数组 什么事情  这里  绝对有些东西 在里面
			if(i>index && arr[i]==arr[i-1]) {
				continue;
			}
			path.add(arr[i]);
			curSum+=arr[i];
			backTracing(arr,target,i,path,ans,curSum);
			path.removeLast();
			curSum-=arr[i];
		}
	}
	
	
	*/
}
